1. Technical Field
This invention relates to information processors, and more particularly to a high speed parallel processor for associating large numbers of high dimensionality data elements.
2. Discussion
High dimensionality data association for large numbers of data elements is one of today's most formidable computing problems These problems typically involve both assignment and correlation tasks. In assignment, a number of data elements are to be selected from among many others and assigned to other elements in such a way as to force the entire assignment over all elements to be optimal in some sense. In correlation problems, elements in one set of data are correlated with elements in another set of data.
These association problems are generally difficult to solve because they are not generally solvable with a single solution but, instead, there may be a range of solutions over which the best solution is sought. Moreover, association problems frequently involve a combinatorial "explosion", or exponential blow up, in the number of possible answers. Association problems are present in a number of applications including, among others, resource allegation, object association, position-only track initiation, deghosting for angle-only targets detected by multiple sensors, pattern matching of two-dimensional feature vectors, template matching, two-dimensional filtering, computerized tomography, manufacturing inspection vision systems and medical image diagnostic systems.
Previous approaches in this area have emphasized solutions in software on both general purpose and special purpose (vector, array, systolic, etc.) computers. The disadvantage of the software approach is that it requires explicit algorithm and software development and massive computational power. In addition, software solutions are not feasible for application to real-time or near real-time problems with large numbers of data elements. For example, a nine dimensional data association problem would require N.sup.9 operations, where N is number of nine dimensional data elements. For problems where N is larger than a few dozen, and where real time operation is required, software solutions simply are not feasible.
Another approach involves the use of connectionist and neural network architectures. Connectionists architecture generally refers to systems which involve massively connected, fine grained processing elements. Neural networks are similar to connectionist architectures, so named because of their similarity to biological networks in their highly interconnected structure and in their ability to adapt to data and exhibit self learning. These approaches have the advantage of operating without requiring the development of an explicit algorithm. For example, see U.S. Pat. No. 4,660,166, issued to J. Hopfield, where a type of neural network is used to solve association problems, such as the traveling salesman problem. Another technique used in connectionist and neural network systems is known as simulated annealing. See S. Kirkpatrick, Gelatt, and Vecchi: "Optimization by Simulated Annealing", 220 SCIENCE, page 671-680 (1983).
Unfortunately, while software simulations of these approaches have been developed, practical hardware versions have not yet been developed which fully realize the potential of these parallel processing approaches. In addition, neural networks such as the one described in U.S. Pat. No. 4,660,166 are generally not fast enough for real-time applications of high dimensionality data association for large numbers of data elements. For example, this system is not able to solve the traveling salesman problem for significantly more than thirty cities.
Thus, it would be desirable to provide an information processor which can solve high dimensionality data association problems for large number of data elements in real-time. It would be desirable to provide an information process that can solve high dimensionality data association problems for a large number data elements which does not require an explicit extensible algorithm development.
Also, it would be desirable to provide such an information processor which can be implemented in current hardware technology and at a reasonable cost.